class Solution
{
public:
    int beautifulPartitions(string s, int k, int minLength)
    {
        return beautifulPartitionsRecursive(s, k, minLength, 0, s.size());
    }

    // 暴力，超时 (而且不一定对)
    int beautifulPartitionsRecursive(string &s, int k, int minLength, int begin, int end)
    {
        if (k == 1)
        {
            if (end - begin < minLength)
            {
                return 0;
            }
            if (!isPrimeDigit(s[begin]) || isPrimeDigit(s[end - 1]))
            {
                return 0;
            }
            return 1;
        }
        if (!isPrimeDigit(s[begin]))
        {
            return 0;
        }
        int result = 0;
        for (int i = begin + minLength - 1; i < end; ++i)
        {
            if (!isPrimeDigit(s[i]))
            {
                result += beautifulPartitionsRecursive(s, k - 1, minLength, i + 1, end);
                result %= 1000000007;
            }
        }
        return result;
    }
};